/**
 * 全排列 2
 *
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * 示例 1：
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 *  [1,2,1],
 *  [2,1,1]]
 *
 * 示例 2：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *
 * 提示：
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 这题的思路和前面一题基本上是完全一样, 我们只需要在特殊的地方剪枝一下就可以了
 * 为啥会有这个特殊的地方呢, 就是因为有重复的数字, 这个时候我们可以画图观察到
 * 在某一个深度遍历的时候要是同一层中出现相同的数字我们只能选其中的一个, 其他的
 * 都需要进行剪枝
 * 还有一种笨的处理方式, 就是我们在最后加入集合的时候判断一下集合中是否已经存过
 * 这个 list, 但是这个方法很笨(尽量不用)
 * 时间复杂度 : O(n^2)
 * 空间复杂度 : O(n^2)
 */

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
        int[] nums = new int[]{1, 1 ,2};
        test.permuteUnique(nums);
    }

    // 依旧全局变量
    static List<List<Integer>> lists;
    static List<Integer> list;
    static int n;
    static boolean[] tmp;

    public List<List<Integer>> permuteUnique(int[] nums) {

        // 初始化
        lists = new ArrayList<>();
        list = new ArrayList<>();
        n = nums.length;
        tmp = new boolean[n];
        Arrays.sort(nums);
        dfs(nums);
        return lists;
    }

    private void dfs (int[] nums) {

        if (list.size() == n) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < n; i++) {

            // 这里怎么进行剪枝, 再强调一遍, 一定要画图画图 !!!!!!!!!!!!!!!!!!!!!!!!!!!
            // 咱承认我们打大脑不好用, 那咋就老老实实的画图来想
            // 我们列 1 1 1 1 2 的图来画, 我们只需要研究明白 2 开头的怎么剪枝好的就可以明白所有的了
            // 首先只看第二层, 全是 1 , 这个时候我们怎么进行剪枝呢, 我们发现只要是和前面相等的数字, 全
            // 都要剪枝, 所以第一个条件 : nums[i] == nums[i - 1]
            // 我们在看第一个 1 的深搜 我们发现这个时候的 nums[i] == nums[i - 1], 但是他是要填 1的
            // 所以我们的条件还是太有限了, 我们需要继续加条件, 这个时候我们看为啥这里不行, 原因是我们已经填过一个 1了
            // 所以我们同时要判断下上一个相同元素是否已经被填过 !tmp[i - 1], 填过才能在继续填一, 这个条件也被上个条件影响
            // 所以这两个条件要一起成立, 才能进行剪枝
            // 我们在回头看一开始的同一层这个条件是否满足, 我们发现这都是被恢复过来的, 所以前面的自然是没填过的, 这个条件直接
            // 就是成立的
            if (i > 0 && nums[i] == nums[i - 1] && !tmp[i - 1]) {
                continue;
            }

            //  这里就是正常的深搜
            if (!tmp[i]) {

                list.add(nums[i]);
                tmp[i] = true;
                dfs(nums);

                // 恢复现场
                tmp[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }



    // *****************************
    // 笨方法
//    List<List<Integer>> lists;
//    List<Integer> list;
//    int n;
//    boolean[] tmp;
//
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        lists = new ArrayList<>();
//        list = new ArrayList<>();
//        n = nums.length;
//        tmp = new boolean[n];
//        dfs(nums);
//        return lists;
//    }
//
//    private void dfs (int[] nums) {
//        if (list.size() == n) {
//            if (!lists.contains(list)) {
//                lists.add(new ArrayList<>(list));
//            }
//            return;
//        }
//        for (int i = 0; i < n; i++) {
//            if (!tmp[i]) {
//                list.add(nums[i]);
//                tmp[i] = true;
//                dfs(nums);
//                list.remove(list.size() - 1);
//                tmp[i] = false;
//            }
//        }
//    }
}